package backtrack;
import java.util.*;
public class _12_47_全排列Ⅱ {
	List<List<Integer>> result = new ArrayList<>();
	List<Integer> item = new ArrayList<>();
	boolean[] use;
    public List<List<Integer>> permuteUnique(int[] nums) {
    	use = new boolean[nums.length];
//    	Arrays.sort(nums);
    	backtracking(nums);
    	
    	return result;
    }
    
    public void backtracking(int[] nums) {
    	
    	if(item.size() == nums.length) {
    		result.add(new ArrayList<>(item));
    		System.out.println(item);
    		return;
    	}
    	// 避免重复的组合，用树层去重
    	// 参考491非递减序列
    	Map<Integer,Integer> map = new HashMap<>();
    	for(int i = 0; i < nums.length; i++) {
    		// 通过use来进行全排列
    		if(use[i]) {
    			continue;
    		}
    		if(map.get(nums[i]) != null) {
    			continue;
    		}
    		item.add(nums[i]);
    		map.put(nums[i], nums[i]);
    		use[i] = true;
    		backtracking(nums);
    		use[i] = false;
    		item.remove(item.size() - 1);
    	}
    	
    	
    }
    
    public static void main(String[] args) {
		int nums[] = {1,2,3};
		new _12_47_全排列Ⅱ().permuteUnique(nums);
	}
}
